package leetcode.year2021.month11;

//  208. 实现 Trie (前缀树)
public class _02_2PrefixTree208 {
  public _02_2PrefixTree208[] children;
  public boolean isEnd;

  public _02_2PrefixTree208() {
    children = new _02_2PrefixTree208[26];
    isEnd = false;
  }

  public void insert(String word) {
    _02_2PrefixTree208 node = this;
    for (int i = 0; i < word.length(); i++) {
      int ch = word.charAt(i);
      int index = ch - 'a';
      if (node.children[index] == null){
        node.children[index] = new _02_2PrefixTree208();
      }
      node = node.children[index];
    }
    node.isEnd = true;
  }

  public boolean search(String word) {
    if (searchPrefix(word) == null){
      return false;
    }
    return searchPrefix(word).isEnd;
  }

  public boolean startsWith(String prefix) {
    return searchPrefix(prefix) != null;
  }

  private _02_2PrefixTree208 searchPrefix(String prefix) {
    _02_2PrefixTree208 node = this;
    for (int i = 0; i < prefix.length(); i++) {
      int ch = prefix.charAt(i);
      int index = ch - 'a';
      if (node.children[index] == null){
        return null;
      }
      node = node.children[index];
    }
    return node;
  }



//  private _02_2PrefixTree208[] children;
//  private boolean isEnd;
//
//  public _02_2PrefixTree208() {
//    children = new _02_2PrefixTree208[26];
//    isEnd = false;
//  }
//
//  public void insert(String word) {
//    _02_2PrefixTree208 node = this;
//    for (int i = 0; i < word.length(); i++) {
//      char ch = word.charAt(i);
//      int index = ch-'a';
//      if (node.children[index] == null){
//        node.children[index] = new _02_2PrefixTree208();
//      }
//      node = node.children[index];
//    }
//    node.isEnd = true;
//  }
//
//  public boolean search(String word) {
//    _02_2PrefixTree208 node = searchPrefix(word);
//    return node != null && node.isEnd;
//  }
//
//  public boolean startsWith(String prefix) {
//    return searchPrefix(prefix) != null;
//  }
//
//  private _02_2PrefixTree208 searchPrefix(String prefix) {
//    _02_2PrefixTree208 node = this;
//    for (int i = 0; i < prefix.length(); i++) {
//      char ch = prefix.charAt(i);
//      int index = ch - 'a';
//      if (node.children[index] == null) {
//        return null;
//      }
//      node = node.children[index];
//    }
//    return node;
//  }

  /**
   * 208. 实现 Trie (前缀树)
   * Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
   *
   * 请你实现 Trie 类：
   *
   * Trie() 初始化前缀树对象。
   * void insert(String word) 向前缀树中插入字符串 word 。
   * boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
   * boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
   *
   *
   * 示例：
   *
   * 输入
   * ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
   * [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
   * 输出
   * [null, null, true, false, true, null, true]
   *
   * 解释
   * Trie trie = new Trie();
   * trie.insert("apple");
   * trie.search("apple");   // 返回 True
   * trie.search("app");     // 返回 False
   * trie.startsWith("app"); // 返回 True
   * trie.insert("app");
   * trie.search("app");     // 返回 True
   *
   *
   * 提示：
   *
   * 1 <= word.length, prefix.length <= 2000
   * word 和 prefix 仅由小写英文字母组成
   * insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次
   */
}
